package problem.ej2;

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;
import java.util.Vector;
import java.util.Iterator;

/*
 * @Grafo: es como representaremos al "grafo" derivado de las conecciones entre investigadores.
 * A cada eje lo guardaremos en la lista de ambos vértices que tiene como extremos
 * Al Grafo lo representaremos como un vector de vértices que contiene una lista de tupla <inicio, destino,entusiasmo>.
 * Obviamente, como no es un digrafo, el destino es una "sobre-notación" ya que no hay destino ni origen (ambos 
 * "salen y llegan").
 * Cosas a tener en cuenta:
 * 1) Hay una biyección entre el nombre del vértice que nos llega y el nombre del vértice del grafo. Es decir, 
 * puede que en la entrada un investigador tenga el nombre "pepe" y en nuestro grafo sea representado por el vértice
 * "10", pero podemos trancisionar entre el "pepe" y el "10" y viceversa sin ambigüedad.
 */
public class Grafo {

	/*
	 * @vertices: es el vector de vértices con el que representaremos a los
	 * vértices propiamente dichos y a los ejes que unen a estos entre sí.
	 */
	private Vector<LinkedList<Integer>> vertices;
	/*
	 * @de_pos_a_investigador_original: Sería como una función biyectiva que
	 * transforma el "nombre" de la localidad provienente del archivo al
	 * "nombre" que le damos nosotros para poder usar la matriz de adyacencia
	 * sin problemas. La posición en el arreglo representa el número que le
	 * damos nosotros para usarlo en el vector "vértices" y el contenido de esa
	 * posición representa el valor original que vino del archivo.
	 */
	private String[] de_pos_a_investigador_original;

	/*
	 * @Constructor: es el constructor de la clase. Recibe como parámetro una
	 * lista de ejes. Cada eje está representado como 2 strings. que representan
	 * a los investigadores.
	 */
	public Grafo(LinkedList<Ejes_strings> lista_adyacencia) {
		/*
		 * 1) Inicializamos el arreglo "de_pos_a_investigador_original" usando un
		 * set para sacar los vértices repetidos
		 * 2) Agregamos los vértices adyacentes a cada vértice en el arreglo "vértices"
		 */
		/*
		 * Primero veo cuántos investigadores distintos hay y le asigno a cada
		 * uno un identificador en el grafo
		 */
		/* |CUIDADO: investigador != eje| */
		TreeSet<String> set_vertices = new TreeSet<String>();//O(1)
		Iterator<Ejes_strings> it_l_ady = lista_adyacencia.iterator();//O(1)
		Ej2.contador_ej2 += 3;
		while (it_l_ady.hasNext()) {
			Ejes_strings amistad = it_l_ady.next();
			set_vertices.add(amistad.inv_1);
			Ej2.contador_ej2 += (int) Math.log(set_vertices.size());
			set_vertices.add(amistad.inv_2);
			Ej2.contador_ej2 += (int) Math.log(set_vertices.size());
			/*
			 * Agrego ambos investigadores. Si ya estaban no importa, de eso se
			 * arregla el Set internamente para no admitir elementos repetidos.
			 */
			Ej2.contador_ej2++;
		}//O(log(investigadores) x cant.amistades)
		/* Ya tengo el set con los vértices sin repetir */
		de_pos_a_investigador_original = new String[set_vertices.size()]; /* lo genero con cantidad de vértices
																		 * sin repetir */
		vertices = new Vector<LinkedList<Integer>>(set_vertices.size()); /*me reserva la capacity para
																		 * el vector */
		/*
		 * ahora lleno el vector con listas vacías para no tener problemas más
		 * adelante
		 */
		Ej2.contador_ej2 += 2 * set_vertices.size();
		for (int i = 0; i < vertices.capacity(); i++)
			vertices.add(new LinkedList<Integer>());
		Ej2.contador_ej2 += vertices.capacity();

		/* Ahora le asigno a cada vértice de mi grafo su respectiva localidad */
		Iterator<String> it_set = set_vertices.iterator();
		for (int i = 0; i < de_pos_a_investigador_original.length; i++) {
			de_pos_a_investigador_original[i] = it_set.next();
			Ej2.contador_ej2++;
		}

		/* Ahora llenamos el vector "vértices" */

		it_l_ady = lista_adyacencia.iterator();
		while (it_l_ady.hasNext()) {
			Ejes_strings amistad = it_l_ady.next();
			int pos_1 = deInvAVertice(amistad.inv_1);//O(investigadores)
			int pos_2 = deInvAVertice(amistad.inv_2);//O(investigadores)

			Integer adyacente_al_1 = new Integer(pos_2);
			Integer adyacente_al_2 = new Integer(pos_1);

			vertices.elementAt(pos_1).add(adyacente_al_1);
			vertices.elementAt(pos_2).add(adyacente_al_2);
			Ej2.contador_ej2 += 8;
		}//O(investigadores * amistades)

	}

	/*
	 * @BFS-mod: Es la función por la que todos pagamos la entrada para venir a
	 * ver. Es donde aplicamos lo interesante del algoritmo: el BFS modificado
	 * para conseguir la fracción de entusiasmo de un investigador comparado con
	 * el otro. Vale lo siguiente (para diferenciar del pseudocódigo): (para
	 * todo x) marcados[x] ==> distancias[x] es la distancia (para todo x)
	 * ¬marcados[x] ==> la distancia es INFINITA
	 */
	int BFS_mod(int p, int q) {
		int[] distancias = new int[vertices.size()];
		boolean[] marcados = new boolean[vertices.size()]; /*
															 * los marcados como
															 * visitados
															 */
		Ej2.contador_ej2 += vertices.size() * 2;
		Queue<Integer> cola_vertices = new LinkedList<Integer>();
		Ej2.contador_ej2 += 1;
		for (int i = 1; i < vertices.size(); i++) {
			marcados[i] = false;
			Ej2.contador_ej2 += 1;
		}
		distancias[p] = 0;
		marcados[p] = true;
		cola_vertices.add(p);
		boolean termino = false;
		Ej2.contador_ej2 += 4;
		while ((!cola_vertices.isEmpty()) && !termino) {
			int v = cola_vertices.poll();
			Iterator<Integer> it = vertices.get(v).iterator();
			Ej2.contador_ej2 += 3;
			while (it.hasNext() && !termino) {
				int w = it.next();
				Ej2.contador_ej2 += 1;
				if (marcados[w] == false) {
					distancias[w] = distancias[v] + 1;
					marcados[w] = true;
					cola_vertices.add(w);
					Ej2.contador_ej2 += 4;
					if (w == q){
						termino = true;
						Ej2.contador_ej2 ++;
					}
				}
			}
		}

		if (marcados[q])
			return distancias[q];
		else
			return 0;
	}

	String deVerticeAInv(int vert) {
		Ej2.contador_ej2 += 1;
		return de_pos_a_investigador_original[vert];
	}

	int deInvAVertice(String inv) {
		/* Complejidad en peor caso: O(cantidad vértices) */

		int res = -1;
		boolean termine = false;
		Ej2.contador_ej2 += 2;
		for (int i = 0; i < de_pos_a_investigador_original.length && !termine; i++) {
			Ej2.contador_ej2 += 1;
			if (de_pos_a_investigador_original[i].equals(inv)) {
				Ej2.contador_ej2 += 2;
				res = i;
				termine = true;
			}
		}
		return res;
	}
	public int getCantVertices(){
		return vertices.size();
	}

}
